package com.zrf.base.knowledge.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * //给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * //
 * // 示例 1:
 * //
 * // 输入: "abcabcbb"
 * //输出: 3
 * //解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: "bbbbb"
 * //输出: 1
 * //解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * //
 * //
 * // 示例 3:
 * //
 * // 输入: "pwwkew"
 * //输出: 3
 * //解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * //     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * //
 * // Related Topics 哈希表 双指针 字符串 Sliding Window
 * // 👍 4322 👎 0
 *
 * @author zhouruifeng
 * @date 2020-09-17 22:26:11
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new LongestSubstringWithoutRepeatingCharacters().new Solution();
        System.out.println(solution.lengthOfLongestSubstring("bbbbb"));;
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));;
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));;
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            Set<Character> characters = new HashSet<>();
            int ans = 0;
            int rank = -1;

            int length = s.length();

            for (int i = 0; i < length; ++i) {
                if (i != 0) {
                    characters.remove(s.charAt(i-1));
                }

                while (rank+1 < length && !characters.contains(s.charAt(rank + 1))) {
                    characters.add(s.charAt(rank + 1));
                    rank++;
                }
                ans = Math.max(ans, rank - i + 1);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}